//
//  17.树的子结构.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/18.
//

import Foundation
/*
 题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 思路：要查找树A中是否存在和树B结构⼀样的⼦树，我们可以分为两步：第⼀步在树A中找到和B的根结点的值⼀样的结点R，第⼆步再判断树A中以R为根节 点的⼦树是不是包含和树B⼀样的结构。 这⾥使⽤递归的⽅法即可。
    
 */
func offer_17() {
    /*
     https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
     */
    print("测试用例查看剑指offer")
}

fileprivate class Solution {
    func hasSubtree(_ pRoot1: BinaryTreeNode<Int>?, _ pRoot2: BinaryTreeNode<Int>?) -> Bool {
        // write code here
        return (pRoot1 != nil && pRoot2 != nil) && (compare(pRoot1, pRoot2) || hasSubtree(pRoot1?.leftNode, pRoot2) || hasSubtree(pRoot1?.rightNode, pRoot2))
    }
    
    func compare(_ nodeA: BinaryTreeNode<Int>?, _ nodeB: BinaryTreeNode<Int>?) -> Bool {
        if nodeB == nil {
            return true
        }
        if nodeA == nil || nodeA?.data != nodeB?.data {
            return false
        }
        return compare(nodeA?.leftNode, nodeB?.leftNode) && compare(nodeA?.rightNode, nodeB?.rightNode)
    }
}


